﻿#define _CRT_SECURE_NO_WARNINGS 1
//https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
//给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


//后序 ：左->右->根
//
//后序的最后一个一定是根，根据后序最后一个在中序中分割左右区间，在根据中序分割的左后区间在后序中分割左右区间。后序左最后一个：左子树跟，后序右最后一个：右子树根
//
//第一步：如果数组大小为零的话，说明是空节点了。
//第二步：如果不为空，那么取后序数组最后一个元素作为头节点元素。
//- 因为后序遍历是 - 左右根，所以最后一个元素就为当前树的根节点，递归到每一个小子树也是一样
//第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
//第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
//- 因为中序左数组对应的后序左数组，数组元素个数肯定是一样的，先切割中序数组，方便后面切割后序数组
//第五步：切割后序数组，切成后序左数组和后序右数组
//第六步：递归处理左区间和右区间


#include<bits/stdc++.h>
using namespace std;
  struct TreeNode {
      int val;
      TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

class Solution {
public:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int inbegin, int inend, int postbegin, int postend)
    {
        if (inbegin > inend) return nullptr;
        TreeNode* root = new TreeNode(postorder[postend]);
        int ini = inbegin;
        while (ini <= inend)
        {
            if (inorder[ini] == root->val) break;
            else ini++;
        }

        //中序 [inbegin ini-1]ini[ini+1 inend]
        //后序 [postbegin(左)  postbegin+中序左区间个数][postbegin+中序左区间个数  postend-1] 根
        root->left = _buildTree(inorder, postorder, inbegin, ini - 1, postbegin, postbegin + ini - 1 - inbegin);
        root->right = _buildTree(inorder, postorder, ini + 1, inend, postbegin + ini - inbegin, postend - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return _buildTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);

    }
};